The present invention generally relates to methods of describing an image, and more particularly to a method of describing an image by a tree structure and applicable to image retrieval, image recognition, image encoding, image transmission, clustering and the like.
Conventionally, as a hierarchical data structure for describing an image, there is a method of describing an image showing in FIG. 1 made up of a plurality of kinds of regions A, B, C, D and E by a four-branch tree structure (so-called guadtree) shown in FIG. 2, for example. According to this system, the image is equally divided (decomposed) into four regions, and each region is recursively and equally subdivided (decomposed) into four subregions until each subregion is made up solely of a single kind of region. The image data storage efficiency of this method is satisfactory, and the method enables basic image processing in the data structure. In addition, the image can be described in levels of rough steps to fine steps. However, as shown in FIG. 2, there is a problem in that a number of nodes increases especially at boundary portions of the data structure. In the four-branch tree structure shown in FIG. 2, three nodes and a leaf branch out from a root node. The node is indicated by a circular mark and corresponds to the region or subregion made up of two or more kinds of regions. On the other hand, the leaf is indicated by a black circular mark and corresponds to the region or subregion made up solely of a single kind of region,.
A method of describing the image by a tree structure having two levels was proposed in "A System of Describing Region Information by a Two-Level Tree Structure" by Osawa et al, Denshi Tsushin Gakkai Ronbunshi, '84/10 Vol. J67-D No.10. According to this proposed method, the tree structure is divded into two levels, and the general information is described by a two-brancah tree structure in a first level while the detail information is described by a simplified two-branch tree structure in a second level. Compared to the conventional method using the four-branch tree structure, the number of nodes is reduced according to this proposed method. However, since the proposed method is based on the two-branch tree structure, there is a problem in that a number of intermediate nodes which are neither a root node nor leaf increases.